home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 285_01 / bisoninf.3 < prev    next >
Text File  |  1990-07-08  |  50KB  |  1,335 lines
  1. Info file bison.info, produced by Makeinfo, -*- Text -*- from input
  2. file bison.texinfo.
  3.  
  4. This file documents the Bison parser generator.
  5.  
  6. Copyright (C) 1988 Free Software Foundation, Inc.
  7.  
  8. Permission is granted to make and distribute verbatim copies of this
  9. manual provided the copyright notice and this permission notice are
  10. preserved on all copies.
  11.  
  12. Permission is granted to copy and distribute modified versions of
  13. this manual under the conditions for verbatim copying, provided also
  14. that the sections entitled ``Bison General Public License'' and
  15. ``Conditions for Using Bison'' are included exactly as in the
  16. original, and provided that the entire resulting derived work is
  17. distributed under the terms of a permission notice identical to this
  18. one.
  19.  
  20. Permission is granted to copy and distribute translations of this
  21. manual into another language, under the above conditions for modified
  22. versions, except that the text of the translations of the sections
  23. entitled ``Bison General Public License'' and ``Conditions for Using
  24. Bison'' must be approved for accuracy by the Foundation.
  25.  
  26.  
  27.  
  28. File: bison.info,  Node: Action Features,  Prev: Error Reporting,  Up: Interface
  29.  
  30. Special Features for Use in Actions
  31. ===================================
  32.  
  33. Here is a table of Bison constructs, variables and macros that are
  34. useful in actions.
  35.  
  36. `$$'
  37.      Acts like a variable that contains the semantic value for the
  38.      grouping made by the current rule.  *Note Actions::.
  39.  
  40. `$N'
  41.      Acts like a variable that contains the semantic value for the
  42.      Nth component of the current rule.  *Note Actions::.
  43.  
  44. `$<TYPEALT>$'
  45.      Like `$$' but specifies alternative TYPEALT in the union
  46.      specified by the `%union' declaration.  *Note Action Types::.
  47.  
  48. `$<TYPEALT>N'
  49.      Like `$N' but specifies alternative TYPEALT in the union
  50.      specified by the `%union' declaration.  *Note Action Types::.
  51.  
  52. `YYABORT;'
  53.      Return immediately from `yyparse', indicating failure.  *Note
  54.      Parser Function::.
  55.  
  56. `YYACCEPT;'
  57.      Return immediately from `yyparse', indicating success.  *Note
  58.      Parser Function::.
  59.  
  60. `YYEMPTY'
  61.      Value stored in `yychar' when there is no look-ahead token.
  62.  
  63. `YYERROR;'
  64.      Cause an immediate syntax error.  This causes `yyerror' to be
  65.      called, and then error recovery begins.  *Note Error Recovery::.
  66.  
  67. `yychar'
  68.      Variable containing the current look-ahead token.  When there is
  69.      no look-ahead token, the value `YYERROR' is stored here.  *Note
  70.      Look-Ahead::.
  71.  
  72. `yyclearin;'
  73.      Discard the current look-ahead token.  This is useful primarily
  74.      in error rules.  *Note Error Recovery::.
  75.  
  76. `yyerrok;'
  77.      Resume generating error messages immediately for subsequent
  78.      syntax errors.  This is useful primarily in error rules.  *Note
  79.      Error Recovery::.
  80.  
  81. `@N'
  82.      Acts like a structure variable containing information on the
  83.      line numbers and column numbers of the Nth component of the
  84.      current rule.  The structure has four members, like this:
  85.  
  86.           struct {
  87.             int first_line, last_line;
  88.             int first_column, last_column;
  89.           };
  90.  
  91.      Thus, to get the starting line number of the third component,
  92.      use `@3.first_line'.
  93.  
  94.      In order for the members of this structure to contain valid
  95.      information, you must make `yylex' supply this information about
  96.      each token.  If you need only certain members, then `yylex' need
  97.      only fill in those members.
  98.  
  99.      The use of this feature makes the parser noticeably slower.
  100.  
  101.  
  102.  
  103. File: bison.info,  Node: Algorithm,  Next: Error Recovery,  Prev: Interface,  Up: Top
  104.  
  105. The Algorithm of the Bison Parser
  106. *********************************
  107.  
  108. As Bison reads tokens, it pushes them onto a stack along with their
  109. semantic values.  The stack is called the "parser stack".  Pushing a
  110. token is traditionally called "shifting".
  111.  
  112. For example, suppose the infix calculator has read `1 + 5 *', with a
  113. `3' to come.  The stack will have four elements, one for each token
  114. that was shifted.
  115.  
  116. But the stack does not always have an element for each token read. 
  117. When the last N tokens and groupings shifted match the components of
  118. a grammar rule, they can be combined according to that rule.  This is
  119. called "reduction".  Those tokens and groupings are replaced on the
  120. stack by a single grouping whose symbol is the result (left hand
  121. side) of that rule.  Running the rule's action is part of the process
  122. of reduction, because this is what computes the semantic value of the
  123. resulting grouping.
  124.  
  125. For example, if the infix calculator's parser stack contains this:
  126.  
  127.      1 + 5 * 3
  128.  
  129. and the next input token is a newline character, then the last three
  130. elements can be reduced to 15 via the rule:
  131.  
  132.      expr: expr '*' expr;
  133.  
  134. Then the stack contains just these three elements:
  135.  
  136.      1 + 15
  137.  
  138. At this point, another reduction can be made, resulting in the single
  139. value 16.  Then the newline token can be shifted.
  140.  
  141. The parser tries, by shifts and reductions, to reduce the entire
  142. input down to a single grouping whose symbol is the grammar's
  143. start-symbol (*note Language and Grammar::.).
  144.  
  145. This kind of parser is known in the literature as a bottom-up parser.
  146.  
  147. * Menu:
  148.  
  149. * Look-Ahead::          Parser looks one token ahead when deciding what to do.
  150. * Shift/Reduce::        Conflicts: when either shifting or reduction is valid.
  151. * Precedence::          Operator precedence works by resolving conflicts.
  152. * Contextual Precedence:: When an operator's precedence depends on context.
  153. * Parser States::       The parser is a finite-state-machine with stack.
  154. * Reduce/Reduce::       When two rules are applicable in the same situation.
  155.  
  156.  
  157.  
  158. File: bison.info,  Node: Look-Ahead,  Next: Shift/Reduce,  Prev: Algorithm,  Up: Algorithm
  159.  
  160. Look-Ahead Tokens
  161. =================
  162.  
  163. The Bison parser does *not* always reduce immediately as soon as the
  164. last N tokens and groupings match a rule.  This is because such a
  165. simple strategy is inadequate to handle most languages.  Instead,
  166. when a reduction is possible, the parser sometimes ``looks ahead'' at
  167. the next token in order to decide what to do.
  168.  
  169. When a token is read, it is not immediately shifted; first it becomes
  170. the "look-ahead token", which is not on the stack.  Now the parser
  171. can perform one or more reductions of tokens and groupings on the
  172. stack, while the look-ahead token remains off to the side.  When no
  173. more reductions should take place, the look-ahead token is shifted
  174. onto the stack.  This does not mean that all possible reductions have
  175. been done; depending on the token type of the look-ahead token, some
  176. rules may choose to delay their application.
  177.  
  178. Here is a simple case where look-ahead is needed.  These three rules
  179. define expressions which contain binary addition operators and
  180. postfix unary factorial operators (`!'), and allow parentheses for
  181. grouping.
  182.  
  183.      expr:     term '+' expr
  184.              | term
  185.              ;
  186.      
  187.      term:     '(' expr ')'
  188.              | term '!'
  189.              | NUMBER
  190.              ;
  191.  
  192. Suppose that the tokens `1 + 2' have been read and shifted; what
  193. should be done?  If the following token is `)', then the first three
  194. tokens must be reduced to form an `expr'.  This is the only valid
  195. course, because shifting the `)' would produce a sequence of symbols
  196. `term ')'', and no rule allows this.
  197.  
  198. If the following token is `!', then it must be shifted immediately so
  199. that `2 !' can be reduced to make a `term'.  If instead the parser
  200. were to reduce before shifting, `1 + 2' would become an `expr'.  It
  201. would then be impossible to shift the `!' because doing so would
  202. produce on the stack the sequence of symbols `expr '!''.  No rule
  203. allows that sequence.
  204.  
  205. The current look-ahead token is stored in the variable `yychar'. 
  206. *Note Action Features::.
  207.  
  208.  
  209.  
  210. File: bison.info,  Node: Shift/Reduce,  Next: Precedence,  Prev: Look-Ahead,  Up: Algorithm
  211.  
  212. Shift/Reduce Conflicts
  213. ======================
  214.  
  215. Suppose we are parsing a language which has if-then and if-then-else
  216. statements, with a pair of rules like this:
  217.  
  218.      i